2.
2022
/
(C++ )
: 3 :75
: - ,
-
1. ? ' - ?
?
2. ? - ?
?
-
3.
?
?
4. ()
() ?
2.
-
5. ?
'
6. ? ?
-
-
7. ? ?
C
8. () ?
() ? ?
, C++
?
2.
2022
/
(C++ )
: 3 :75
: - ,
-
1. ? ' - ?
?
: ?
:
•
10 , 10 ,
• -
• ( )
,
5 :
[0] [1] [2] [3] [4]
' 0 , 1
:
1, 2, 3, 4, 5
2.
:
[5]
, - !
'
- - , ,
- -
- :
,
,
:
• (- )
• ( ' )
2.
:
:
1.
2. ( )
5 , '
3.
' ,
4.
( )
, -
,
1.
,
, !
,
2.
2.
,
3.
( , , )
-- ,
5 ,
:
:
• A
• n
• pos
•
:
→
i = n – 1
i >= pos
2.
• A[i] A[i + 1]
• i 1
pos → A[pos] = '
n 1 ( )
!
-
:
•
•
2. ? - ?
?
:-
, ,
,
', ,
,
-
,
( )
--
?
2.
• : , ,
• : ( 25, 100), (""), , ,
•
"" - , ,
?
• :
•
: ( , )
( , )
- ,
:
1.
•
• : , , ,
•
2. -
:
a)
• ,
• :
o : -
o : ,
o :LIFO ( , )
o :FIFO ( , )
' —
2.
b) -
•
;
• :
o : ( )
o : ( )
- -
c) -
• '
• :
'
?
, :
?
• - ,
•
:
1. :
2. :
:
•
- , ( )
•
( ) ,
?
1. :
o
(, )
2. (n):
o
o : n
3. , :
2.
o :
( ,
)
o :- ( , ' )
o :
,
1. O (O)
• ( )
• : → O(n)
• :
"
"
2. (Ω)
• ( )
• : → Ω(1) '
"-
"
3. (Θ)
•
( )
• : → Θ(log n)
"
' "
:
•
- , O(n) —
•
3 , Ω(1) —
•
' , Θ(n/2) —
2.
-
'
, ,
, ,
,
-
/
,
()
O(n)
(Ω)
Ω(1)
(Θ)
-
Θ(log n)
-
;
, , ,
,
,
-
3.
?
?
: ?
'
:
FIFO - ,
:
• =
2.
• =
,
:
• ()
•
:
•
•
'
' :
( )
?
'
:
10, 20, 30
:
• → 10
• → 30
40
, 30 :
10, 20, 30, 40
40
,
, :
2.
( )
?
FRONT
:
10, 20, 30, 40
:
• 10
• 20
:
20, 30, 40
:
;
;
?
;
:
2.
- ,
5 5
: 0 1 2 3 4
: - - - - -
:
• →
• →
:
= -1
= -1
()
:
1.
2. →
3.
4. '
5. , = 0
: 10
= 0
= 0
: 10 - - - -
20
= 0
= 1
: 10 20 - - -
30
= 0
= 2
: 10 20 30 - -
2.
()
:
1.
2. →
3.
4.
:
10 20 30
= 0
= 2
→ 10
= 1
= 2
: - 20 30 - -
10 ,
' ,
,
, ,
:
•
•
•
:
•
•
:
2.
•
•
:
•
• '
•
:
1.
2.
3.
4. '
5. ,
: 10
→ 10 → NULL
→ 10
20
→ 10 → 20 → NULL
→ 20
30
→ 10 → 20 → 30 → NULL
→ 30
:
1.
2.
3. '
4.
2.
10:
: 10 → 20 → 30
: 20 → 30
→ 20
:
• NULL
• NULL
?
-
:
, ,
'
CPU
2.
✔
✔FIFO - '
✔ REAR '
✔ FRONT '
✔ :
✔ :
• ( )
• ( )
4. ()
() ?
:-
,
,
, --,
A:
1. ?
--
"" , ,
' :
()
, ,
-
2.
2.
1. : ( ' , ,
)
2. : ,
3. : - '
4. : - ,
3.
: [35, 12, 43, 8, 51]
1: , 51,
2:
• 51 → [35, 12, 43, 8]
• → 51
• 51 → []
: [35, 12, 43, 8] | 51 | []
3: [35, 12, 43, 8]
• = 8
• 8 → []
• 8 → [35, 12, 43]
• : [] | 8 | [35, 12, 43]
4: [35, 12, 43]
• = 43
• 43 → [35, 12]
• 43 → []
• : [35, 12] | 43 | []
5: [35, 12]
• = 12
• 12 → []
• 12 → [35]
• : [] | 12 | [35]
4.
2.
: [8, 12, 35, 43, 51]
- -
5.
•
• : O(n log n)
• - (
)
6.
• : O(n²) ( )
•
:
1. ?
, ,
: 3 + 4 ,
+ 3 4
2.
1. ():
o : + 3 4 → 3 + 4
2. ( ):
o : 3 4 + → 3 + 4
' ,
3.
: (5 + 6) * 7
• () : (5 + 6) * 7
• : * + 5 6 7
2.
:
• , + 5 6 5 + 6 = 11
• , *11 7 11 * 7 = 77
77
4.
: (5 + 6) * 7
• : 5 6 + 7 *
:
• , 5 6 + → 11
• , 11 7 * → 77
, 77
5.
•
•
•
(5 + 6) * 7 ,
: " ?"
* + 5 6 7 , :
1. 5 6
2. 7
-
[35, 12, 43, 8, 51] → [8, 12, 35, 43,
51]
2.
* + 5 6 7
5 6 + 7 *
,
O(n n)
,
,
-
5. ?
'
: ? ( )
,
?
,
, , ,
, ,
- ( , ) -
' -,
, :
→ →
( )
:
25, 10, 55, 30, 5
2.
1:
5
(25) 5
:
5, 10, 55, 30, 25
5 '
2:
:
10, 55, 30, 25
10 , '
:
5, 10, 55, 30, 25
3:
:
55, 30, 25
25
55 25 - :
5, 10, 25, 30, 55
4:
:
30, 55
30 ,
2.
, 55
, :
5, 10, 25, 30, 55
- -
,
():
1.
2. '
3.
4. , '
5. '
6.
':
i = 0 n-2
- = i
j = i+1 n-1
[j] < [- ]
- = j
[i] [minIndex]
:
•
•
•
•
•
-!
2.
'
:
:
( ) ?
:
• ,
(n − 1)
• ,
(n − 2)
• ,
(n − 3) , ...
:
(n − 1) + (n − 2) + (n − 3) + ... + 1
:
n(n − 1) / 2
, :
(²)
:
• = O(n²)
• = O(n²)
• = O(n²)
:
(1)
-
2.
1.
2.
3.
4. ,
5. - (
)
-
' ,
-
, ?
:
•
•
•
, ,
O(n²)
,
,
6. ? ?
-
2.
:-
-
,
,
,
, ,
-
:
?
• :
•
• ,
,
: ( ) ,
?
:
1. :
o
o
2. :
o ,
3. :
o
4. :
o
5. :
o
2.
: [5, 12, 23, 34, 45, 56, 67, 78, 89]
45
1: = 34 ( 3)
• 45 > 34 ,
2: - = [45, 56, 67, 78, 89]
• = 67
• 45 < 67 ,
3: - = [45, 56]
• = 56
• 45 < 56 ,
4: - = [45]
• = 45
• 4 '
: 45 4 '
(C- )
( [], , ) {
= 0;
= n - 1;
( <= ) {
= ( + ) / 2;
(arr[mid] == )
; //
(arr[mid] < target )
= + 1; //
= - 1; //
}
2.
-1; //
}
-- :
:
1. : = 0 = n - 1
2. <= : a. : mid = (low + high) / 2. b.
arr[mid] == target , mid c. arr[mid] <target , set low = mid +
1 d. arr[mid] > target , set high = mid - 1
3.
, -1
78 : [5, 12, 23, 34, 45, 56, 67, 78, 89]
• 1:
o = 0, = 8, = 4
o arr[mid] = 45 78 > 45
o
: = 5, = 8
• 2:
o = (5 + 8) / 2 = 6
o arr[mid] = 67 78 > 67
o
: = 7, = 8
• 3:
o = (7 + 8) / 2 = 7
o arr[mid] = 78.
: 78 7 '
• :
o : O(1) ( )
o : O(log n) ( )
o : O(log n)
2.
• :
o : O(1)
o : O(log n) ( )
(O(n))
1 100
,
,
50, 75,
62, 7 ,
-
1
2
3
4
5
' ,
, , - '
-
7. ? ?
C
: ?
, -
, ""
2.
•
•
•
, , ' -
"" :
=
=
, " "
, , , '
,
,
-
,
-
', :
- ( )
:
•
•
, C C++ '
- ' C
C++
- ( )
, ,
' C++ OOP
2.
, C
, C ,
C " "
, C -
C
?
C C++ -
,
:
•
•
-
,
- : -
:
•
•
"" , : (),
'
C
C
C
:
# <stdio.h>
//
() {
printf(" \n");
}
//
() {
2.
printf(" \n");
}
//
{
(*)(); //
};
() {
//
1;
2;
//
1. = ;
shape2.draw = ;
// -
printf(" 1:");
1. ();
printf(" 2: ");
2.();
0;
}
( )
:
,
stdio.h
printf
:
• drawCircle() → “Drawing a Circle”
• drawRectangle() → “ ”
-
struct Shape :
(*)();
2.
:
•
•
•
-
main():
:
1;
2;
:
1. = ;
shape2.draw = ;
:
• 1
• 2
,
:
1. ();
2.();
draw() ,
! →
:
1:
2:
?
:
2.
-
-
8. () ?
() ? ?
, C++
?
:-
C++ - (OOP)
OOP /
( +, -, *)
- ' , OOP
- -
:
,
A:
1. ?
• C++ -
• ', + - ( , )
,
: ,
c1 + c2
' +
2.
?
•
• c1.add(c2) ,
c1 + c2
• -
2.
3.
# <iostream>
std ;
{
, ;
:
( = 0, = 0) {
= r;
= i;
}
// +
+ (const &obj) {
;
. = + .;
. = + .;
;
}
() {
cout << << " + " << << "i" << endl;
}
};
() {
c1(3, 4), c2(1, 2);
c3 = c1 + c2; // +
c3.display(); // : 4 + 6i
0;
}
4.
•
•
+
•
c1 + c2 , ,
• 4 + 6i
2.
:
1. ?
•
• ( ) ( )
• : , , () ()
,
2. ?
•
• -
• : , myCar = =
120 /
3.
• ;
• ,
,
• , -
: = = , , -
4. C++
# <iostream>
std ;
//
{
;
;
:
2.
//
( n, a) {
= n;
= a;
}
//
() {
cout << ": " << << ", : " << << endl;
}
};
() {
//
s1, s2;
//
s1.setData("", 20);
s2.setData("", 19);
//
s1.display(); // : : , : 20
s2.display(); // : : , : 19
0;
}
5.
•
Student class
•
s1 s2
• ,
• ,
,
/
,
,
,
2.
-
,
,
,
, ,
• - -
,
• OOP
, -
• , C++ , ,
: ,
"
,
"
